#include <set>
#include <vector>
#include <map>
using namespace std;

class Solution {
public:

    //剑指 Offer 03. 数组中重复的数字
    int findRepeatNumber(vector<int>& nums) {
        set<int> dict;
        for (auto num : nums)
        {
            if (!(dict.insert(num).second))
                return num;
        }
        return -1;
    }

//////////////////////////////////////////////////////////

    //剑指 Offer 53 - I. 在排序数组中查找数字 I
    //法一
    // int search(vector<int>& nums, int target) {
    //     map<int, int> hash;
    //     for (auto& num : nums)
    //     {
    //         ++hash[num];
    //     }
    //     return hash[target];
    // }
    //法二
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0)
            return 0;
        auto it = lower_bound(nums.begin(), nums.end(), target);
        int count = 0;
        while (it != nums.end() && *it == target)
        {
            ++count;
            ++it;
        }
        return count;
    }

///////////////////////////////////////////////////////////////////

    //剑指 Offer 53 - II. 0～n-1中缺失的数字
    int missingNumber(vector<int>& nums) {
        int n = nums.size() + 1;
        for (int i = 0; i<n-1; ++i)
        {
            if (nums[i] != i)
                return i;
        }
        return n-1;
    }
};